package com.lee.algorithm.recursion;

/***
 * @description 斐波那契数列
 * @author 青石路
 * @date 2022/1/6 17:23
 */
public class Fibonacci {

    /**
     * 暴力递归
     *      容易实现、容易理解
     *      但执行时间长
     * @param n
     * @return
     */
    public static long fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }


    public static long fibonacciPlus(int n) {
        if (n < 1) {
            return 0;
        }
        long[] cache = new long[n + 1];
        return fibonacciPlusSupport(n, cache);
    }

    private static long fibonacciPlusSupport(int n, long[] cache) {
        if (n == 1 || n == 2) {
            return 1;
        }

        // 已经计算过，直接返回
        if (cache[n] != 0) {
            return cache[n];
        }

        // 没计算过
        cache[n] = fibonacciPlusSupport(n-1, cache) + fibonacciPlusSupport(n-2, cache);
        return cache[n];
    }

    /**
     * 动态规划
     * @param n
     * @return
     */
    public static long fibonacciDp(int n) {
        long dp[] = new long[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i=3; i<=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    /**
     * 从下往上 递推
     * @param n
     * @return
     */
    public static long fibonacciIterate(int n) {
        if (n <= 2) {
            return 1;
        }
        long f1 = 1;
        long f2 = 1;
        long sum = 0;
        for (int i=3; i<=n; i++) {
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        long fibonacci = fibonacci(40);
        long end = System.currentTimeMillis();
        System.out.println("结果 = " + fibonacci + " ,花费时长：" + (end - start) + " 毫秒");

        start = System.currentTimeMillis();
        fibonacci = fibonacciPlus(40);
        end = System.currentTimeMillis();
        System.out.println("结果 = " + fibonacci + " ,花费时长：" + (end - start) + " 毫秒");

        start = System.currentTimeMillis();
        fibonacci = fibonacciIterate(40);
        end = System.currentTimeMillis();
        System.out.println("结果 = " + fibonacci + " ,花费时长：" + (end - start) + " 毫秒");
    }
}
